package demo16;

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {

        int[] nums = {-100,-98,-2,-1};
        System.out.println(threeSumClosest(nums,-101));
    }

    public static int threeSumClosest(int[] nums, int target) {
        if(nums.length == 3){
            //数组的长度只有3，那只有一个结果集，直接返回即可
            return nums[0]+nums[1]+nums[2];
        }else{
            //对数组进行排序
            Arrays.sort(nums);
        }

        if(nums[0] >= target && target >=0){
            //如果排序后的第一数就已经比target大了，那么前三个数的合一定是最接近target的
            //注意：这里的规则只适合正数，负数就不是这样了
            return nums[0]+nums[1]+nums[2];
        }else if(nums[nums.length-1] <= target && target <=0){
            //当目标值是负数的时候，排序后的数组右边界的值比目标值还要小，那么最后三个数的合一定是最接近target的
            return nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3];
        }
        int min = nums[0]+nums[1]+nums[2];//定义当前最接近的数
        int size = Math.abs(min-target);//获得当前距离
        int left,right;//定义左指针和右指针
        //排除掉以上的特殊情况，开始正常的查找
        for (int i = 0; i < nums.length-2; i++) {
            if(i!=0 && nums[i] == nums[i-1]){
                continue;
            }
            //当i指向正数的时候，后续的结果集不可能符合结果，所以条件判断写nums[i] <= 0
            left = i+1;//重新给左指针赋值
            right = nums.length-1;//重新给右指针赋值
            while(left < right){
                //开始对i，left，right所指向的数做判断
                if(Math.abs(nums[i]+nums[left]+nums[right]-target) < size){
                    //找到更接近的数
                    size = Math.abs(nums[i]+nums[left]+nums[right]-target);
                    min = nums[i]+nums[left]+nums[right];
                }

                if(nums[i]+nums[left]+nums[right] < target){
                    //比目标值要小，需要左指针右移，让合变大
                    left++;
                }else if(nums[i]+nums[left]+nums[right] > target){
                    //比目标值要大，需要右指针左移，让合变小
                    right--;
                }else{
                    //nums[i]+nums[left]+nums[right] == target，直接返回target即可
                    return target;
                }
            }
        }
        return min;
    }
}
